#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 460. LFU 缓存.py
@time: 2022/3/7 14:58
@desc: https://leetcode-cn.com/problems/lfu-cache/
> 请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。

实现 LFUCache 类：

LFUCache(int capacity) - 用数据结构的容量capacity 初始化对象
int get(int key)- 如果键key 存在于缓存中，则获取键的值，否则返回 -1 。
void put(int key, int value)- 如果键key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。
为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。
当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

1. key哈希表，频率哈希表，存放双向链表
2. https://leetcode-cn.com/problems/lfu-cache/solution/chao-xiang-xi-tu-jie-dong-tu-yan-shi-460-lfuhuan-c/
'''


class Node:
    def __init__(self, key=None, value=None, freq=0):
        self.key = key
        self.value = value
        self.freq = freq
        self.next = None
        self.prev = None


class LinkedList:
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def insertFirst(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def delete(self, node):
        if self.isEmpty(): return
        node.next.prev = node.prev
        node.prev.next = node.next
        del node

    def getLast(self):
        if self.isEmpty(): return
        return self.tail.prev

    def isEmpty(self):
        return self.head.next == self.tail


class LFUCache:

    def __init__(self, capacity: int):
        # 需要：
        #   1. 容量
        #   2. key->Node的哈希表
        #   3. freq->LinkedList的哈希表，即维护频率相关的双向链表
        #   4. 当前的最低频率
        self.capacity = capacity
        self.keyMap = {}
        self.freqMap = {}
        self.minFreq = 0

    def get(self, key: int) -> int:
        # 获取元素，key不存在则返回-1，否则返回value
        # 更新被访问元素的频率，即自增1的频率
        if not key in self.keyMap: return -1
        node = self.keyMap[key]
        self.increaseFreq(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        # 插入指定key和value，key存在则直接更新value，同时更新频率
        # key不存在：
        #   1. 缓存没满：直接插入
        #   2. 缓存满了，删掉频率最低，且位于频率哈希表所指链表的尾部的元素，插入元素
        if key in self.keyMap:
            node = self.keyMap[key]
            node.value = value
            self.increaseFreq(node)
        else:
            if self.capacity==0: return
            # 满了
            if len(self.keyMap) == self.capacity:
                self.removeMinFreqNode()
            node = Node(key, value, 1)
            self.increaseFreq(node, True)
            self.keyMap[key] = node

    def increaseFreq(self, node, isNewNode=False):
        # 更新结点的访问频率
        if isNewNode:
            self.minFreq = 1
            self.setLinkedList(node)
        else:
            # 更新频率，因此要删除该结点
            self.deleteNode(node)
            node.freq += 1
            self.setLinkedList(node)
            if self.minFreq not in self.freqMap:
                self.minFreq += 1

    def setLinkedList(self, node):
        # 根据node的频率将结点插入应去的双向链表
        if node.freq not in self.freqMap:
            self.freqMap[node.freq] = LinkedList()
        linkedList = self.freqMap[node.freq]
        linkedList.insertFirst(node)

    def deleteNode(self, node):
        # 将当前结点从其所在链表摘除
        if not node.freq in self.freqMap:
            return
        linkedList = self.freqMap[node.freq]
        freq = node.freq
        # 删掉这个结点
        linkedList.delete(node)
        # 如果该频率下的链表已经无了，就清楚这个key
        if linkedList.isEmpty():
            del self.freqMap[freq]

    def removeMinFreqNode(self):
        # 删除最久最少访问结点
        linkedList = self.freqMap[self.minFreq]
        # 获取尾部结点，因为都是头插，所以尾部一定是最久未访问的
        node = linkedList.getLast()
        linkedList.delete(node)
        # 删掉他的映射
        del self.keyMap[node.key]
        if linkedList.isEmpty():
            del self.freqMap[node.freq]

# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

if __name__ == '__main__':
    obj = LFUCache(0)
    obj.put(0,0)
    obj.get(0)